package main

// 本题是 462
// https://leetcode-cn.com/problems/minimum-moves-to-equal-array-elements/solution/

// 求 pivot
func Pivotikey(nums []int, left, right int) int {
	pivot := nums[right]
	i := left
	for j := left; j < right; j++ {
		if nums[j] < pivot {
			nums[i], nums[j] = nums[j], nums[i]
			i++
		}
	}
	nums[i], nums[right] = nums[right], nums[i]
	return i
}

func selector(nums []int, left, right int) int {
	mid := Pivotikey(nums, left, right)
	if left <= right {   // 注意这里和 快排的区别， 相等时 还要进行判断。
		if mid == len(nums)/2 { // 默认是整数，不用类型转换
			return nums[mid]
		} else if mid < len(nums)/2 {
			return selector(nums, mid+1, right)
		} else {
			return selector(nums, left, mid-1)
		}
	}
	return 0
}


func minMoves2(nums []int) int {
	// 求中位数
	n := selector(nums, 0, len(nums) - 1)
	rst := 0
	// 求结果
	for _, num := range nums {
		if num > n {
			rst += num - n
		} else {
			rst += n - num
		}
	}
	return rst
}
